# coding=utf-8

"""
原地反转一个链表

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode* new_list = NULL;

    while (head != NULL) {
        struct ListNode* elem = head;
        head = head->next;

        elem->next = new_list;
        new_list = elem;
    }

    return new_list;
}


// 迭代的版本
void reverse(Node*& head) {
  if (!head)
    return;

  Node* prev = NULL;
  Node* curr = head;

  while (curr) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }

  head = prev;
}

// 递归的版本
void reverse(Node*& p) {
    if (!p)
        return;

    Node* rest = p->next;

    if (!rest)
        return;

    reverse(rest);

    p->next->next = p;
    p->next = NULL;
    p = rest;
}
"""


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def print_list(l1):
    list_str = ""

    while l1:
        list_str = "[%s] ->" % l1.val
        print list_str,
        l1 = l1.next

    print "None",


def reverse_list2(head):
    pass


def reverse_list(head):
    if head is None:
        return None

    prev = None
    curr = head

    while curr is not None:
        next = curr.next
        curr.next = prev

        prev = curr
        curr = next

    return prev


if __name__ == "__main__":
    l1 = ListNode(1)
    _l1 = l1
    l1.next = ListNode(0)
    l1 = l1.next
    l1.next = ListNode(2)
    l1 = l1.next
    l1.next = ListNode(4)
    l1 = l1.next

    print_list(reverse_list(_l1))
